package com.fps.webshop.question.question0800_0899;

import java.util.Arrays;

/**
 * 881. 救生艇
 * 
 * 第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
 * 
 * 示例 1：
 * 输入：people = [1,2], limit = 3
 * 输出：1
 * 解释：1 艘船载 (1, 2)
 * 
 * 示例 2：
 * 输入：people = [3,2,2,1], limit = 3
 * 输出：3
 * 解释：3 艘船分别载 (1, 2), (2) 和 (3)
 * 
 * 示例 3：
 * 输入：people = [3,5,3,4], limit = 5
 * 输出：4
 * 解释：4 艘船分别载 (3), (3), (4), (5)
 * 
 * 提示：
 * 		1 <= people.length <= 50000
 * 		1 <= people[i] <= limit <= 30000
 */
public class Question881 {
	
	/**
	 * 第一次提交，先排序，再比较，但排序耗时比较大
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		19 ms	47.4 MB	Java	2021/08/26 10:46
	 * 
	 * 执行用时：19 ms, 在所有 Java 提交中击败了19.40%的用户
	 * 内存消耗：47.4 MB, 在所有 Java 提交中击败了36.04%的用户
	 */
	public static int numRescueBoats(int[] people, int limit) {
		Arrays.sort(people);
		int boat = 0;
		int start = 0;
		int end = people.length-1;
		while(start<=end) {
			if(people[end]+people[start]<=limit) {
				boat++;
				end--;
				start++;
			}else {
				boat++;
				end--;
			}
		}
		return boat;
    }
	
	/**
	 * 第2一次提交，网友的神奇代码，快很多，100人之下直接排序，100人以上动态规划
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	46.6 MB	Java	2021/08/26 10:58	
	 * 
	 * 执行用时：3 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：46.6 MB, 在所有 Java 提交中击败了97.33%的用户
	 */
	public int numRescueBoats2(int[] people, int limit) {
        if(people.length<=100){
            Arrays.sort(people);
            int i=0,j=people.length-1,cnt=0;
            while(i<j){
                if(people[i]+people[j]<=limit){i++;}
                j--;
                cnt++;
            }
            return i==j?cnt+1:cnt;
        }else{
            int[] buckets=new int[limit+1];
            for(int person:people){
                buckets[person]++;
            }
            int i=1,j=limit,cnt=0;
            while(i<j){
                while(i<j && buckets[i]==0) i++;
                while(i<j && buckets[j]==0) j--;
                if(i+j<=limit){buckets[i]--;}
                buckets[j]--;
                cnt++;
            }
            if(i==j){
                if(i*2<=limit){
                    cnt+=(buckets[i]+1)>>1;
                }else{
                    cnt+=buckets[i];
                }
            }else{cnt--;}
            return cnt;
        }
    }
	
	/**
	 * 第3次提交，网友的更神奇代码，貌似用了动态规划
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		2 ms	46.7 MB	Java	2021/08/26 10:56
	 * 
	 * 执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：46.7 MB, 在所有 Java 提交中击败了95.84%的用户
	 */
	public int numRescueBoats3(int[] people, int limit) {
        //因为数组中的数字是小于等于limit
        int[] dp = new int[limit + 1];
        //计数排序
        for (int person : people) {
            dp[person]++;
        }
        int left = 0;
        int right = limit;
        int ans = 0;
        //双指针
        while (left < right) {
            //因为中间会有很多 0 （因为数组中没有这个数，导致计数排序计算不到这个数的数量，所以为0）
            //这种数是无效的 直接跳过
            while (left < right && dp[right] == 0) right--;
            while (left < right && dp[left] == 0) left++;
            //这句主要是防止再走一遍 下面的逻辑 尽早退出循环
            //把 left == right 这种情况放到循环外面去计算 不然每次循环都要判断
            if (left == right) {
                break;
            }
            //因为已经排好序的 所以 right 就表示最右边的数
            //如果大于等于 limit 说明这条船只能这个人坐 所以 ans+=dp[right]
            //这里直接清0 防止重复计算 (因为下个循环进来还是同样的情况)
            if (right >= limit) {
                ans += dp[right];
                dp[right] = 0;
                //判断这船能否坐一个大的一个小的
                //如果 两个加起来 超过了 limit 说明 这个right匹配不到人 ans+=dp[right]
                //这里直接清0 防止重复计算(因为下个循环进来还是同样的情况)
            } else if (right + left > limit) {
                ans += dp[right];
                dp[right] = 0;
            } else {
                //这里表示可以匹配一个right 一个left
                //直接计算 能匹配多少个 right+left
                int min = Math.min(dp[left], dp[right]);
                ans += min;
                if (dp[left] == min){
                    dp[left] = 0;
                    dp[right] -= min;
                }else {
                    dp[right] = 0;
                    dp[left] -= min;
                }
            }
        }
        //计算 left 与 right 重合的情况
        if (left == right) {
            ans += left * 2 > limit ? dp[left] : (dp[left] & 1) == 1 ? dp[left] / 2 + 1 : dp[left] / 2;
        }
        return ans;
    }
	
	public static void main(String[] args) {
		int[] people = new int[] {3,5,3,4};
		System.out.print(numRescueBoats(people,5));
	}
}
